In communications systems, Local Area Networks (LANs) provide communication between a limited number of stations located within a limited geography. A single LAN is known as a LAN segment, and a group of LANs joined together by one or more bridges or routers is known as an extended LAN. A typical LAN segment may connect hundreds of stations over a distance of several kilometers. A bridge or router may be used to connect multiple LAN segments, providing communication between a larger number of stations over a larger area, and preventing excessive local traffic from degrading overall network performance. In the text below, the term "bridge" is meant to indicate either a bridge or router.
A bridge monitors the traffic on all the LAN segments to which it is attached, and determines a destination segment (or segments) for each received frame. The determination of a destination segment for a received frame is hereinafter referred to as a "forwarding decision". The bridge uses the addressing information in the received frame to locate forwarding information in a forwarding database to make the forwarding decision for that received frame.
Forwarding decisions must be made at the maximum frame transmission rate of the attached LAN segments. Otherwise the bridge is a limitation on network throughput. To meet this performance requirement, especially where high speed fiber optic based LANs are used, forwarding decisions are commonly done in customized frame forwarding hardware, known as Application Specific Integrated Circuits (ASICS).
The addressing information of each frame consists of various address fields within the frame, including a destination station address. The forwarding information for a station address is contained in a forwarding entry for that station address. Each forwarding entry contains an address field and a forwarding information field. The forwarding information field contains forwarding information for frames addressed to the station address in the address field. As stations are added to and removed from the LAN segments attached to the bridge or router, forwarding entries are added and deleted from the forwarding database.
In known forwarding database designs, the forwarding database is designed as an ordered list. When a new station address is added to the forwarding database, a binary search is performed to find the location for the new forwarding entry. Potentially all the current forwarding entries must be moved to accommodate the new forwarding entry. Such implementations require excessive processing resources, and are not practical in environments with frequent additions of new station addresses, and where the forwarding database is very large.
Other known forwarding database designs use Content Addressable Memory (CAM) to store the forwarding database. However, CAM based implementations are often prohibitively costly in terms of circuit complexity and expense.
In other forwarding database designs, forwarding entries for sets of related addresses are grouped into variable sized forwarding entry sets. Each forwarding entry set consists of a contiguous block of memory within a forwarding table, and contains forwarding entries for a set of related addresses. When a forwarding entry is added, the forwarding entry set for that forwarding entry requires a larger segment of forwarding table memory. If the forwarding entry set cannot grow in its current location, a new segment of forwarding table memory must be allocated. The forwarding entry set is then moved to the new segment. The original location of the forwarding entry set becomes free memory space, and may subsequently be allocated to another forwarding entry set.
Over time, as forwarding entries are added to the forwarding database, and large segments of forwarding table memory are allocated to accommodate the larger forwarding entry sets, the number of small free segments of forwarding table memory increases, and the number of large free memory segments decreases. This is known as memory fragmentation. Memory fragmentation eventually results in a deficiency of large free memory segments. Thereafter, when a new forwarding entry is added to the forwarding database, there may be no contiguous free memory segment large enough to store the new forwarding entry set containing the forwarding entry for the new address. This event may occur even though the total amount of free memory in the forwarding table is sufficient to store the forwarding entry set, but the free memory is broken up into many small non-contiguous segments. Therefore, memory fragmentation results in poor utilization of forwarding table memory space, and puts an artificial limit on the number of forwarding entries that can be stored in the forwarding database. An efficient forwarding database design therefore requires a method to reduce memory fragmentation.
The necessity of using ASICs to perform forwarding decisions in bridges for newer high speed LANS introduces further requirements on forwarding database designs. Generally in ASIC design, the more logic gates in the design, the higher the cost of the implementation. Moreover, the more circuit complexity within the ASIC, the greater the development time, and amount of testing and verification required before the ASIC can be brought to market. Therefore limiting complexity of the circuit design, and limiting the number of gates in each ASIC are design priorities to reduce the cost of the ASIC, the time to bring the ASIC to market, and the probability of design failure.
In modern ASIC design, multiple logic processes exist within the ASIC, each logic process performing a specific function. Logic processes communicate with other logic processes and outside the device through registers. Registers create circuit complexity, and add to the number of gates within the ASIC. Accordingly, minimizing the size and number of registers in the ASIC reduces the ASIC cost.
While forwarding decisions are made by the forwarding ASIC, forwarding table management is done in parallel by software running on a microprocessor. Thus the forwarding table may be accessed to perform a forwarding decision while the memory fragmentation within the forwarding table is being reduced. A method to reduce memory fragmentation must assure that the forwarding entry sets within the forwarding table are not invalid. Otherwise, forwarding decisions could not be made, and received frames would not be forwarded, or possibly, forwarded incorrectly.
Finally, where forwarding database management is performed by a process running on a microprocessor, the management process must be triggered to reduce fragmentation before the forwarding table is highly fragmented. And the management process should terminate without causing other processes that require the microprocessor to be unable to make to progress for an excessive period of time.
For these reasons and others, a high speed bridge having a free space collection system is required, which reduces memory fragmentation within the forwarding database of the bridge, limits the number of gates required in the forwarding ASIC, and maintains the validity of the forwarding entry sets during operation so that forwarding decisions can be made in parallel. The free space collection method should be triggered prior to memory fragmentation becoming extreme, and should execute such that shared resources can be used by other processes, and starvation does not result.